// https://leetcode.cn/problems/missing-number/

// 题干：给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数

// 示例：输入：nums = [3,0,1]
//       输出：2

// 碎语：异或性质：a^a=0，既然[0,n]之间的数字缺少了一个，那么先全部异或，再异或数组元素
//       最后结果必是没出现过的数字，这种方法还利用了异或的结合律

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int missingNumber(vector<int>& nums)
    {
        int ret = 0;

        for (int i = 0 ; i < nums.size() ; i++){
            ret ^= nums[i];
            ret ^= i;
        }
        ret ^= nums.size();

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {3,0,1};

    cout << sol.missingNumber(nums) << endl;

    return 0;
}